A navigation system performs travel guidance for enabling a user to easily and quickly reach the selected destination. A typical example is a vehicle navigation system where a vehicle is equipped with a navigation function to guide a user to a destination through a calculated route. Such a navigation system detects the position of the user's vehicle, and reads out map data pertaining to an area at the current vehicle position from a data storage medium, for example, a CD-ROM (compact disc read-only memory), a DVD (digital versatile disc), or a hard disc. Typically, the navigation system displays a map image on a monitor screen while superimposing thereon a mark representing the current location of the user. At an intersection, the navigation system notifies the user which direction to turn at the intersection.
Typically, a navigation system stores the map data which is in a multiple-level (layered) structure that stores links, nodes and other information for each layer of the map data. For calculating a route between the start point and the end point (destination), the navigation system checks various possible links starting from both the start point and the end point with use of, for example, an A* algorithm. Such an example is shown in FIGS. 1A and 1B where the navigation system simultaneously searches a route from the vehicle position (start point) VP to the destination (end point) Dst. Two elliptic marks A1 and A2 indicate general search directions and search areas for the search operations using the A* algorithm.
The elliptic marks A1 and A2 are established from the vehicle position VP toward the destination Dst and vice versa to limit the search directions and search areas. As the search progresses, the segments of routes from the vehicle position VP and from the destination Dst meet to create a complete route (calculated route) that connects the current vehicle position VP and the destination Dst. During this process, the navigation system attempts to climb up to the map data of upper layer, which generally has a network of higher class routes and thus fewer links (nodes), to speed up the process of searching a route as well as to find a quicker route, for example, using freeways.
FIGS. 2A and 2B are schematic diagrams showing a situation wherein an inefficient route can be produced when searching links in the map data of layered structure. As shown in the arrows of FIG. 2A, a route 21 makes a right turn at the second street and comes back to the same point indicated by a circle 22 through the first street before proceeding to the north (upper direction). Such an inefficient and unwanted route is caused because of an inappropriate climbing point between the two layers of different level of the map data as will be explained below with reference to FIG. 2B.
FIG. 2B shows an upper layer 59A, a middle layer 59B, and a lower layer 59C of the map data, which is directed to the situation where the navigation searches links in the lower layer 59C and the middle layer 59B. In general, due to the smaller number of links in a higher layer, the route calculation covering the same range is more efficiently conducted at an upper level. Thus, it is preferable that the route search operation be conducted at the higher level if there is a node that can allow the process to climb to the upper layer of the map data.
In the example of FIG. 2B, the lower layer 59C includes links L01-L03, L11, L21-25 and L31 each being connected at corresponding nodes N. Some nodes, such as a node N01 or a node N33, are climbing-up points each allowing climbing up or down between the two different layers. The node N01 in the lower layer 59C allows the route to climb up to an upper node N11 in the middle layer 59B as indicated by the dotted line. In this example, a start point 19 is on the link L21 in the lower layer 59C.
The links L11 and L21-L25 in the lower layer 59C correspond to the links L200 in the upper layer 59A and the link L20 in the middle layer 59B. In other words, the road expressed by the links L200 and L20 in the upper layer 59A and the middle layer 59B and the road expressed by the links L11 and L21-25 in the lower layer 59C are the same such as a freeway or a high class street. In the lower layer of map data, such a road is configured by many links of relatively short length while the same road is configured by a small number of relatively long links in the higher layer of the map data.
In the route calculation process, the navigation system will explore possible links and weigh the cost of each link to find the route between the start point and the destination. After the link L21, the link L03 and the link L22 are possible link candidates. For exploring the route via the link L03, the candidate route is the link L02, and then the link L01. At the end of the link L01, the node N01 allows the route to climb-up to the upper node N11 on the middle layer 59B. On the other hand, exploring the route through the link L22, the next link is L23, and then, the link L24, and so on.
When both routes are explored, if the first route comprising link L03, L02, and L01 which has the climbing-up node N01 is found to exist, the climbing-up operation will take priority. That is, when the climb up node N01 is found while the node N29 fails to climb to an upper node, the tendency is to prioritize the node N01. This is true even if the second route comprising the links L22, L23, etc. is eventually able to reach the node N33 that allows climbing-up to the upper node N35, since the node N29 is outside of the predetermined search range 75. Thus, the second route will no longer be taken into consideration for route calculation and the link data associated with the second route will be deleted.
However, the first route causes the inefficient route as shown in FIG. 2A by returning to the point that has already passed. Thus, there is a need for a new route search method for a navigation system that overcomes the shortcoming described above.